package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var maxLen = 0

func longestZigZag(root *TreeNode) int {
	maxLen = 0
	if root.Left != nil {
		goLeft(root.Left, 0)	
	}
	if root.Right != nil {
		goRight(root.Right, 0)
	}
	return maxLen
}


func goLeft(node *TreeNode, len int) {
	if node == nil {
		return
	}
	len++
	if len > maxLen {
		maxLen = len
	}
	if node.Left != nil {
		goLeft(node.Left, 0)
	}
	if node.Right != nil {
		goRight(node.Right, len)
	}
}

func goRight(node *TreeNode, len int) {
	if node == nil {
		return
	}
	len++
	if len > maxLen { 
		maxLen = len
	}
	if node.Left != nil {
		goLeft(node.Left, len)
	}
	if node.Right != nil {
		goRight(node.Right, 0)
	}
}

func main() {
	tree := &TreeNode{
		Right: &TreeNode{
			Left: &TreeNode{},
			Right: &TreeNode{
				Left: &TreeNode{
					Right: &TreeNode{
						Right: &TreeNode{},
					},
				},
				Right: &TreeNode{},
			},
		},
	}
	// tree = &TreeNode{}
	ret := longestZigZag(tree)
	println(ret)
}